package leecode

import (
	"strconv"
)

func Clumsy(n int) int {
	count := 1
	str := strconv.Itoa(n)
	for i := n - 1; i > 0; i-- {
		switch count {
		case 1:
			//temp = temp * i
			str = str + "*" + strconv.Itoa(i)
			//使用 *
			count++
		case 2:
			str = str + "/" + strconv.Itoa(i)
			// 使用 /
			count++
		case 3:
			// 使用+
			str = str + "+" + strconv.Itoa(i)
			count++
		case 4:
			str = str + "-" + strconv.Itoa(i)
			// 使用 -
			count = 1
		}
	}
	arr := nifixToRPN([]byte(str))
	result := evalRpn(arr)
	return result
}

// 中缀表达式转化为后缀表达式
func nifixToRPN(nifix []byte) []string {
	operatorStack := make([]byte, 0, 20)    //用于存放运算符的栈
	result := make([]string, 0, len(nifix)) //后缀表达式
	//priority 存放运算符优先级
	priority := map[byte]int{
		'+': 0,
		'-': 0,
		'*': 1,
		'/': 1,
	}
	i := 0
	//处理第一个数为负数的情况
	if nifix[0] == '-' {
		i = 1
		tempI := i
		//处理'-'后的数字加入result
		for tempI+1 < len(nifix) && nifix[tempI+1] >= '0' && nifix[tempI+1] <= '9' {
			tempI++
		}
		result = append(result, "-"+string(nifix[i:tempI+1]))
		i = tempI + 1
	}
	for ; i < len(nifix); i++ {
		//将连续的数字写入result
		if nifix[i] >= '0' && nifix[i] <= '9' {
			tempI := i
			for tempI+1 < len(nifix) && nifix[tempI+1] >= '0' && nifix[tempI+1] <= '9' {
				tempI++
			}
			result = append(result, string(nifix[i:tempI+1]))
			i = tempI
			continue
		}
		//把括号里面的内容当成一个数字 , 将得到的逆波兰表达式直接写入result
		if nifix[i] == '(' {
			//消除括号
			newNifix, last := barket(nifix, i)
			result = append(result, newNifix...)
			i = last
			continue
		}
		//栈中没有运算符 , 直接将当前运算符入栈
		if len(operatorStack) == 0 {
			operatorStack = append(operatorStack, nifix[i])
			continue
		}
		//如果当前运算符的优先级 小于 上一个符号优先级 , 则将栈清空 , 当前符号入栈
		if priority[nifix[i]] < priority[operatorStack[len(operatorStack)-1]] {
			//清空栈,将其写入到result
			for len(operatorStack) != 0 {
				result = append(result, string(operatorStack[len(operatorStack)-1]))
				operatorStack = operatorStack[0 : len(operatorStack)-1]
			}
			//当前符号入栈
			operatorStack = append(operatorStack, nifix[i])
			continue
		}
		//如果当前运算符优先级 等于 上一个符号优先级 , 栈中优先级相同的连续符号全部出栈
		if priority[nifix[i]] == priority[operatorStack[len(operatorStack)-1]] {
			for len(operatorStack) != 0 && priority[nifix[i]] == priority[operatorStack[len(operatorStack)-1]] {
				result = append(result, string(operatorStack[len(operatorStack)-1]))
				operatorStack = operatorStack[0 : len(operatorStack)-1]
			}
			//当前符号入栈
			operatorStack = append(operatorStack, nifix[i])
			continue
		}
		//此时栈中还有符号 , 且当前符号优先级高于栈中符号 , 当前符号入栈
		operatorStack = append(operatorStack, nifix[i])
	}
	//检测是否还有符号未出栈,有测依次出栈
	if len(operatorStack) != 0 {
		if len(operatorStack) == 2 {
			result = append(result, string(operatorStack[1]))
		}
		result = append(result, string(operatorStack[0]))
	}
	return result
}

// 递归消除括号 , 返回对应的括号位置
func barket(a []byte, first int) ([]string, int) {
	last := 0  //对应后括号的位置
	count := 0 //计数左括号
	for i := first; i < len(a)-1; i++ {
		if a[i+1] == '(' {
			count++
		}
		if a[i+1] == ')' {
			if count == 0 {
				last = i + 1
				break
			} else {
				count--
			}
		}
	}
	newA := a[first+1 : last]
	return nifixToRPN(newA), last
}

// 后缀表达式求值
func evalRpn(tokens []string) int {
	if len(tokens) == 1 {
		temp, _ := strconv.Atoi(tokens[0])
		return temp
	}
	var result int
	prn := make([]int, 0, len(tokens))
	for _, value := range tokens {
		if value == "+" {
			//取出栈顶的两个元素相加
			result = prn[len(prn)-1] + prn[len(prn)-2]
			//将得到的结果压栈
			prn = prn[:len(prn)-2]
			prn = append(prn, result)
		} else if value == "-" {
			//取出栈顶的两个元素相减
			result = prn[len(prn)-2] - prn[len(prn)-1]
			//将结果压栈
			prn = prn[:len(prn)-2]
			prn = append(prn, result)
		} else if value == "*" {
			//取出栈顶的两个元素相乘
			result = prn[len(prn)-1] * prn[len(prn)-2]
			//将结果压栈
			prn = prn[:len(prn)-2]
			prn = append(prn, result)
		} else if value == "/" {
			result = prn[len(prn)-2] / prn[len(prn)-1]
			//将结果压栈
			prn = prn[:len(prn)-2]
			prn = append(prn, result)
		} else {
			temp, _ := strconv.Atoi(value)
			prn = append(prn, temp)
		}
	}
	return result
}
